package Leetcode.lc018;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 四数之和
 */

public class Sloution {

    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res=new ArrayList<>();
        Arrays.sort(nums);
        for(int k=0;k<nums.length;k++){
            //开始剪枝
            if(nums[k]>target && nums[k]>=0){
                break;
            }
            //去重
            if(k>0 && nums[k]==nums[k-1]){
                continue;
            }
            for(int i=k+1;i<nums.length;i++){
                //继续剪枝
                if(nums[k]+nums[i]>target && nums[k]+nums[i]>=0){
                    break;
                }
                //去重
                if(i>k+1 && nums[i]==nums[i-1]){
                    continue;
                }
                int left=i+1;
                int right=nums.length-1;
                while(right>left){
                    //注意溢出
                    long sum=(long)nums[k]+nums[i]+nums[left]+nums[right];
                    if(sum>target) right--;
                    else if(sum<target) left++;
                    else{
                        res.add(Arrays.asList(nums[k],nums[i],nums[left],nums[right]));
                        //去重
                        while(right>left && nums[right]==nums[right-1]) right--;
                        while(right>left && nums[left]==nums[left+1]) left++;
                        right--;
                        left++;
                    }
                }

            }
        }
        return res;
    }
    public static void main(String[] args) {
        Sloution sloution = new Sloution();
        int[] ints = {1, 0, -1, 0, -2, 2};
        List<List<Integer>> result=sloution.fourSum(ints,1);
        for(List<Integer> a:result){
            System.out.print(a);
        }
    }
}
